package 图;

import com.alibaba.fastjson.JSON;
import javafx.util.Pair;

import java.util.*;

public class No399除法求值 {

    /**
     * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，
     * 其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。
     * 每个 Ai 或 Bi 是一个表示单个变量的字符串。
     * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，
     * 请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
     * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。
     * 如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
     * 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
     * <p>
     * 示例 1：
     * 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","A"],["a","a"],["x","x"]]
     * 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
     * 解释：
     * 条件：a / b = 2.0, b / c = 3.0
     * 问题：a / c = ?, b / a = ?, a / A = ?, a / a = ?, x / x = ?
     * 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
     * 示例 2：
     * 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
     * 输出：[3.75000,0.40000,5.00000,0.20000]
     * 示例 3：
     * 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
     * 输出：[0.50000,2.00000,-1.00000,-1.00000]
     *  
     * 提示：
     * 1 <= equations.length <= 20
     * equations[i].length == 2
     * 1 <= Ai.length, Bi.length <= 5
     * values.length == equations.length
     * 0.0 < values[i] <= 20.0
     * 1 <= queries.length <= 20
     * queries[i].length == 2
     * 1 <= Cj.length, Dj.length <= 5
     * Ai, Bi, Cj, Dj 由小写英文字母与数字组成
     */

    static class Node {
        /**
         * 当前节点的值
         */
        private String c;
        /**
         * 值-权重 : 节点
         */
        private Map<Pair<String, Double>, Node> map;

        private Node(String c, Map<Pair<String, Double>, Node> map) {
            this.c = c;
            this.map = map;
        }
    }

    /**
     * 草稿纸上画好图来,即可求解
     *
     * @param equations
     * @param values
     * @param queries
     * @return
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        double[] result = new double[queries.size()];
        Map<String, Node> nodeMap = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            String str1 = equations.get(i).get(0);
            String str2 = equations.get(i).get(1);
            //获取节点1
            Node node1 = nodeMap.computeIfAbsent(str1, key -> new Node(str1, new HashMap<>()));
            //存入权重边
            node1.map.put(new Pair<>(str2, values[i]), nodeMap.computeIfAbsent(str2, key -> new Node(str2, new HashMap<>())));
            //反向也记得存上
            Node node2 = nodeMap.get(str2);
            node2.map.put(new Pair<>(str1, 1 / values[i]), node1);
        }

        //存入完毕,开始遍历问题
        for (int i = 0; i < queries.size(); i++) {
            String str1 = queries.get(i).get(0);
            String str2 = queries.get(i).get(1);

            if (!nodeMap.containsKey(str1) || !nodeMap.containsKey(str2)) {
                result[i] = -1;
                continue;
            }

            if (str1.equals(str2) && nodeMap.containsKey(str1)) {
                result[i] = 1;
                continue;
            }

            //开始dfs去搜索答案吧 需要Set,避免绕路
            //从str1的节点开始搜索
            Double itemResult = this.dfs(1, nodeMap.get(str1), str2, new HashSet<>(), nodeMap.size());
            result[i] = itemResult == null ? -1 : itemResult;
        }

        return result;
    }

    private Double dfs(double product, Node node, String targetStr, Set<String> set, int maxLength) {

        for (Map.Entry<Pair<String, Double>, Node> entry : node.map.entrySet()) {
            Pair<String, Double> pair = entry.getKey();
            if (pair.getKey().equals(targetStr)) {
                //找到了目标节点了 就返回
                return product * pair.getValue();
            }
            //没有找到,那么继续dfs
            //过滤已经找过的节点
            if (set.contains(pair.getKey())) {
                continue;
            }
            set.add(pair.getKey());
            Double result = this.dfs(product * pair.getValue(), entry.getValue(), targetStr, set, maxLength);
            if (result != null) {
                return result;
            }
        }

        /**
         * 没有爆满,就继续遍历下去,直到第一层遍历完毕到下方的null为止
         */
        if (set.size() == maxLength) {
            return -1D;
        }

        return null;
    }

    public static void main(String[] args) {
        No399除法求值 n = new No399除法求值();
        List<List<String>> equations = Arrays.asList(Arrays.asList("a", "b"), Arrays.asList("c", "d"));
        double[] values = new double[]{2.0, 3.0};
        List<List<String>> queries = Arrays.asList(Arrays.asList("a", "c"), Arrays.asList("b", "a"), Arrays.asList("a", "A"), Arrays.asList("a", "a"), Arrays.asList("x", "x"));
        double[] result = n.calcEquation(equations, values, queries);
        System.out.println(JSON.toJSONString(result));
    }

}
